\documentclass{ita}
\usepackage{amsmath}
\usepackage{amssymb,amsfonts,amsthm}
\usepackage{gastex}
\usepackage[english]{babel}
\usepackage{graphicx}
\usepackage{cite}               
\tolerance=1000


\begin{document}
%%-----------------------------
%%      the top matter
%%-----------------------------
\title{On Abelian Repetition Threshold}
\runningtitle{On Abelian Repetition Threshold}
%
\author{Alexey V. Samsonov, Arseny M. Shur}\address{Ural State University, Ekaterinburg, Russia; vonosmas@gmail.com, Arseny.Shur@usu.ru}
%
\date{}
%
\begin{abstract} 
We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.\,e., a numerical value separating $k$-avoidable and $k$-unavoidable Abelian powers for each size $k$ of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional power. We develop a method estimating the exponential growth rate of Abelian-power-free languages. Using this method, we get non-trivial lower bounds for Abelian repetition threshold for small alphabets. We suggest that some of the obtained bounds are the exact values of Abelian repetition threshold. In addition, we provide upper bounds for the growth rates of some particular Abelian-power-free languages.
\end{abstract}
%
\subjclass{68Q70, 68R15}
%
\maketitle


\section*{Introduction}

The study of avoidable powers of words has more than a centennial history since the paper by Thue \cite{Th}. Recall that for any finite word $w$ its 2nd power (or \textit{square}) is just the word $ww$, denoted by $w^2$, its 3rd power (or \textit{cube}) is $w^3=www$, and so on. Further, the notion of integral power of a word can be easily generalized to non-integral powers as follows. If $w$ is a word, $|w|$ is its length, $\beta>1$ is a number, then $w^{\beta}$ is a unique prefix $v$ of the infinite word $www\ldots$, whose length satisfies the conditions $|v|/|w|\ge\beta$, $(|v|{-}1)/|w|<\beta$. A word $u$ is \textit{$\beta$-free}, if none of its factors, including $u$ itself, is a $\beta$-power. A $\beta$-power is said to be \textit{$k$-avoidable} if there are infinitely many $\beta$-free words (or, equivalently, an infinite $\beta$-free word) over the $k$-letter alphabet, and \textit{$k$-unavoidable} otherwise.

For any $k$-letter alphabet ($k\ge2$), the \textit{repetition threshold} is the number $RT(k)$ which separates $k$-unavoidable and $k$-avoidable powers of words. Famous Dejean's conjecture \cite{Dej} states that $RT(3)=7/4$, $RT(4)=7/5$, and $RT(k)=k/(k{-}1)$ otherwise. The recent proof of this conjecture (see \cite{Car, CR, Rao}) closed a whole chapter in combinatorics on words but also opened a way to new challenging problems. One of these problems is to obtain a similar characterization of power-free languages in the Abelian case.

Abelian powers of words were first considered by Erd\"os \cite{Erd} as a natural generalization of ``usual'' powers.
The word $w_1w_2\ldots w_n$ is an \textit{Abelian $n$-th power}, if each of the words $w_2,\ldots,w_n$ is an anagram of $w_1$.
Equivalently, one can say that $w_1=w_2=\ldots=w_n$ in any commutative semigroup, or that $w_1,\ldots,w_n$ share the same Parikh vector. It is clear that, in contrast with the usual powers, there are several ways to generalize the notion of Abelian power to fractional exponents. Below we define weak, semistrong and strong Abelian fractional powers and then work with all three definitions.

The avoidability of Abelian integral powers is well studied.
It is easy to check that Abelian squares are 3-unavoidable and Abelian cubes are 2-unavoidable. On the other hand, the language of all quaternary Abelian-square-free words is infinite \cite{Ker} and even has exponential growth \cite{Car1, Ker2}. The same is true for ternary Abelian-cube-free and binary Abelian-4-free languages, see \cite{Dek} for infiniteness and \cite{ACR,Cur} for exponential growth. However, the obtained bounds for the exponential growth rate are difficult to use for estimating the actual growth rates of these languages. We shall give such estimations as an implementation of a more general method we present in this paper. While \cite{ACR,Car1,Cur,Ker2} give lower bounds for the growth rates, this method is used for calculating the upper bounds.

Once a definition of Abelian fractional power is chosen, Abelian repetition threshold can be defined in the same way as the ``usual'' repetition threshold. We study the values of Abelian repetition threshold for all alphabets and three different definitions of Abelian fractional power. The paper contains both analytic and computer-assisted results.

A method to obtain upper bounds for the growth rates of power-free languages is proposed in \cite{Sh10tcs}. On the base of this method we construct our main instrument, which is a method to obtain upper bounds for the growth rates of \textit{Abelian}-power-free languages. 


\section{Preliminary considerations}

We omit basic definitions on words and languages, assuming that the reader is familiar with them.
Let $\Sigma=\{1,\ldots,k\}$ be an alphabet and $w\in\Sigma^*$ be an arbitrary $k$-ary word. The Parikh vector $\vec p(w)$ is the vector of length $k$ whose $i$-th component equals the number of occurrences of the letter $i$ in $w$, for any $i=1,\ldots,k$. If $v\in\Sigma^*$ is a $k$-ary word, then notation $\vec p(w) \le \vec p(v)$ means that $i$-th component of $\vec p(w)$ is not greater than $i$-th component of $\vec p(v)$, for any $i=1,\ldots,k$.

A language $L\subseteq\Sigma^*$ is \textit{factorial} if it is closed under taking factors of its words. A word $w$ is {\it forbidden} for a language $L$ if it is a factor of no word from $L$. The set of all minimal (with respect to the factor order) forbidden words for $L$ is called the {\it antidictionary} of $L$.
A factorial language $L\subseteq\Sigma^*$ with the antidictionary $M$ satisfies the equalities $L=\Sigma^*-\Sigma^*\!M\Sigma^*$, $M=\Sigma L\cap L\Sigma\cap(\Sigma^*{-}L)$. Thus, each antidictionary determines a unique factorial language, which is regular if the antidictionary
is also regular (in particular, finite). 

\begin{rmrk} \label{infad}
Infinite regular languages contain arbitrarily big powers of words. If an infinite language $L$ has finite antidictionary, then $L$ is regular and can't be a power-free language. Hence, infinite power-free (or Abelian-power-free) languages have infinite antidictionaries.
\end{rmrk}

The ``size'' of a language $L$ can be expressed by its \textit{combinatorial complexity}, which is the function $C_L(n)=|\Sigma^n\cap L|$. \textit{Growth rate} of $L$ roughly describes the behaviour of combinatorial complexity and is defined by the equality $\alpha(L) = \limsup\limits_{n\to\infty}(C_L(n))^{1/n}$. If a regular language $L$ is given by a deterministic finite automaton (dfa) $\cal A$ with the property that each vertex is visited during at least one successful computation, then $\alpha(L)$ coincides with the \textit{Frobenius root} (or \textit{spectral radius}) of the adjacency matrix of $\cal A$. This result is probably folklore; a short proof of it can be found in \cite{Sh08ita}. The dfa's with the mentioned property are said to be \textit{consistent}.

\smallskip\noindent{\bf1.1. Abelian powers. }
Let $m \ge 2$ be an integer. As we have said above, an \textit{Abelian m-power} is a word of the form $w_{1}w_{2} \ldots w_{m}$, where $w_{i}$ is an anagram of $w_{1}$ for $2 \le i \le m$, or, in other words, $\vec p(w_1)=\ldots=\vec p(w_m)$. Now we extend this definition to the rational numbers in the range $(1,\infty)$. Let $\beta > 1$,  $|w_1|=q$, $m=\lfloor\beta\rfloor$, $t=\lceil\{\beta\}q\rceil$, where $\{\beta\}$ stands for the fractional part of $\beta$. Consider a word of the form $w = w_{1} \ldots w_{m}v$, where $w_{1} \ldots w_{m}$ is an Abelian $m$-power and $|v| = t$. Throughout this paper, the terms \textit{root} and \textit{tail} with respect to Abelian power denote the words $w_{1}$ and $v$ respectively. Clearly, to call the word $w$ an Abelian $\beta$-power we should impose an additional restriction upon the Parikh vector of the tail. We consider three different such restrictions, thus obtaining three definitions of Abelian fractional power. Let $\mathrm{pref}(u, l)$ be the prefix of length $l$ of the word $u$.

A \textit{weak Abelian $\beta$-power} is a word $w$ of the form described above such that $\vec p(v)\le\vec p(w_1)$. That is, the tail is a prefix of an anagram of the root.

A \textit{strong Abelian $\beta$-power} is a word $w$ of the form described above such that $\vec p(v)=\vec p(\mathrm{pref}(w_1,t))$. That is, the tail is an anagram of a prefix of the root. However, in this definition we clearly distinguish the root among all words $w_{i}$, since the tail does not depend on the order of letters in $w_{i}$ for $2 \le i \le m$. After swapping $w_{1}$ and $w_{2}$ the word may lose (or gain) its property of being a strong Abelian power. For example, the word $abc\,cab\,ba$ is a strong Abelian $8/3$-power, while the word $cab\,abc\,ba$ is not. To remedy this, we introduce the following definition:

A \textit{semistrong Abelian $\beta$-power} is a word $w$ of the form described above such that $\vec p(v)\le\!\!\bigvee\limits_{i=\overline{1,m}}\!\!\vec p(\mathrm{pref}(w_i,t))$, where $\bigvee$ is the operation of taking maximum componentwise.
Thus, all $w_i$'s are used symmetrically in the restriction imposed upon the tail, like in the definition of the weak powers.

\begin{rmrk} \label{abel1}
(1) For integral values of $\beta$ all three definitions are equivalent to the definition of the integral Abelian power.\\
(2) For $\beta \le 2$ the definitions of strong and semistrong Abelian $\beta$-powers are equivalent.\\
(3) Every strong Abelian $\beta$-power is also a semistrong Abelian $\beta$-power, and every semistrong Abelian $\beta$-power is also a weak Abelian $\beta$-power.
\end{rmrk}

\begin{xmpl}
The word $abc\,cba\,ac$ is a semistrong Abelian $(8/3)$-power and is also a weak Abelian $(8/3)$-power, but not
a strong Abelian $(8/3)$-power, because $ac$ is not a permutation of $ab$. The word $abcaa$ is not even a weak Abelian $(5/3)$-power,
but is a strong, semistrong and weak Abelian $(5/4)$-power.
\end{xmpl}

\begin{rmrk} \label{abel2}
There are several possible ``symmetrizations'' of the notion of strong Abelian $\beta$-power. The above notion of semistrong Abelian $\beta$-power uses the ``weakest'' restriction on $\vec{p}(v)$. It will be seen in Section~4 that the suggested values of Abelian repetition threshold coincide for strong and semistrong powers. So, if we are aimed at Abelian repetition threshold, it makes no sense to study other symmetrizations.
\end{rmrk}

\noindent{\bf1.2. Abelian-power-free languages. }
\textit{Abelian exponent} of a word $w \in \Sigma^{*}$ is the maximal rational number $\beta$ such that $w$ is an Abelian $\beta$-power.
A word $w$ is called \textit{Abelian-$\beta$-free} (\textit{Abelian-$\beta^{+}\!$-free}) if all its factors have Abelian exponents less than $\beta$ (respectively, at most $\beta$). It is convenient to use only the term $\beta$-free, assuming that $\beta$ belongs to the set of ``extended rationals''. This set consists of all rational numbers and all such numbers with a plus; the number $x^+$ covers $x$ in the usual $\le$ order in a way that the inequalities $y\le x$ and $y<x^+$ are equivalent. By \textit{Abelian-$\beta$-free languages} we mean the languages of \textit{all} Abelian-$\beta$-free words over a given alphabet. These languages are factorial and are called \textit{Abelian-power-free} languages. We consider three types of Abelian-power-free languages (weak, semistrong and strong), corresponding to the three definitions of fractional Abelian powers. When necessary, we add the attribute strong (semistrong, weak) to any of the defined notions to specify the type of Abelian power.

To compare these definitions, it is reasonable to compare the sizes of the corresponding Abelian-power-free languages. Thus, we need a method for estimating the growth rates of the Abelian-power-free languages for weak, semistrong and strong Abelian powers. First, recall the method of \cite{Sh10tcs} for power-free languages.

\smallskip\noindent{\bf1.3. Estimating growth rates of power-free languages. }To obtain the upper bounds for the growth rates of factorial languages one can use languages with finite antidictionary as follows. Let $L\subseteq\Sigma^*$ be a factorial language with the antidictionary $M$. Consider a family $\{M_i\}$ of finite subsets of $M$ such that
$$
M_1\subseteq M_2\subseteq\dotsb\subseteq M_i\subseteq\dotsb\subseteq M,
\quad M_1\cup M_2\cup\dotsb\cup M_i\cup\dotsb=M. 
$$
Denote by $L_i$ the factorial language over $\Sigma$ with the antidictionary $M_i$. One has
$$
L\subseteq\dotsb\subseteq L_i\subseteq\dotsb\subseteq L_1,
\quad L_1\cap L_2\cap\dotsb\cap L_i\cap\dotsb=L.
$$
It is not hard to show that the sequence $\{\alpha(L_i)\}$ decreases and converges to $\alpha(L)$. Since the languages $L_i$ are regular, the number $\alpha(L_i)$ can be found with any degree of precision. Increasing $i$, one can make the upper bound arbitrarily close to $\alpha(L)$. 

Thus, to obtain an upper bound for $\alpha(L)$ one should make three steps. First, build the antidictionary $M_i$ for the chosen $i$. Second, convert this antidictionary into a consistent deterministic finite automaton (dfa) recognizing $L_i$. And finally, calculate the number $\alpha(L_i)$.

For a power-free (say, $\beta$-free) language these steps can be made as follows. We define $M_i$ to be the set of all minimal forbidden words $u^{\beta}$ such that $|u|\le i$, calculate $M_i$ by some advanced search procedure and store it as a trie. Then we use a modification of the Aho-Corasick algorithm for pattern matching to convert the trie into the consistent dfa recognizing $L_i$. Finally, we calculate $\alpha(L_i)$ with any prescribed precision by an efficient (linear in the size of the automaton) iterative algorithm. One can improve the above scheme and shrink the sizes of the trie and the automaton by the factor of almost $|\Sigma|!$. This improvement can be adopted for any factorial language $L$ which is \textit{symmetric} in the sense that $u\in L$ implies $\sigma(u)\in L$ for any permutation $\sigma$ of the alphabet. This property allows one to represent any equivalence class of symmetric words by a single word. So, we build only the words from the antidictionary which are lexicographically minimal in their symmetry classes (these words form a ``subtrie'' of the whole trie) and represent the transitions in the whole automaton by transitions between the vertices of this subtrie. In what follows, the words forming this subtrie are referred to as \textit{lexmin words}.

The mentioned algorithms for the second and third steps can be used for any symmetric factorial language. However, the first step can vary significantly for different subclasses of factorial languages.

In practice, the described method for power-free languages works well enough, allowing one to construct and handle huge automata in a short time. So, if we can efficiently organize the first step for Abelian-power-free languages, we will get a very powerful instrument.



\section{Lower bounds for Abelian repetition threshold}

Like Dejean in \cite{Dej}, we begin the study of the Abelian repetition threshold with the lower bounds. Let $\Sigma=\{1,\ldots,k\}$. We prove uniform lower bounds for both strong and weak Abelian repetition threshold (denoted by $ART_s(k)$ and $ART_w(k)$, respectively). In view of the numerical results of Section 4, it looks highly probable that our bound for $ART_s(k)$ is exact, while the bound for $ART_w(k)$ can be improved. In what follows, we prove

\begin{thrm} \label{art_strong}
$ART_{s}(k) \ge \frac{k{-}2}{k{-}3}$ for all $k \ge 5$.
\end{thrm}

Let $w = w_{1} \ldots w_{m} \in\Sigma^*$, where $w_{1},\ldots,w_{m}$ are letters in $\Sigma$. We say that a factor $u$ of the word $w$ is an \textit{l-factor} if $|u| = l$. The $j$th $l$-factor is the factor $w_{j} \ldots w_{j{+}l{-}1}$. For any $j$, the $j$th and $(j{+}1)$th $l$-factors of $w$ are called \textit{successive}. We need two lemmas.

\begin{lmm} \label{lemma_art_strong1}
Suppose that $k \ge 4$, $w \in \Sigma^*$ is a strong (=semistrong) Abelian-$\frac{k{-}2}{k{-}3}$-free word. 
\begin{itemize}
\item[(1)] Each $(k{-}2)$-factor of $w$ consists of $(k{-}2)$ different letters;
\item[(2)] At least one of any two successive $(k{-}1)$-factors of $w$ consists of $(k{-}1)$ different letters.
\end{itemize}
\end{lmm}

\begin{proof}
(1) Let $w =w_1\ldots w_m$. If $w_i=w_j$, $i<j$, then $w_i\ldots w_j$ is an Abelian $\frac{j{-}i{+}1}{j{-}i}$-power. Since $w$ is Abelian-$\frac{k{-}2}{k{-}3}$-free, we get $j{-}i\ge k{-}2$, whence the result.

(2) Let $u = w_{i} \ldots w_{i+k{-}2}$ and $v = w_{i+1} \ldots w_{i+k{-}1}$ be two successive $(k{-}1)$-factors of $w$. Since $u$ and $v$ are Abelian-$\beta$-free, it follows from (1) that the first $(k{-}2)$ letters of $u$ are different, as well as the last $(k{-}2)$ letters of both $u$ and $v$. Suppose that both $u$ and $v$ contain equal letters. This can happen only if $w_{i} = w_{i+k{-}2}$ and $w_{i+1} = w_{i+k{-}1}$, which implies that the word $w_{i} \ldots w_{i+k{-}1}$ is a strong Abelian $\frac{k}{k{-}2}$-power. Since $\frac{k}{k{-}2}\ge \frac{k{-}2}{k{-}3}$ for $k \ge 4$, $w$ is not Abelian-$\frac{k{-}2}{k{-}3}$-free, and we get a contradiction. Hence, either $u$ or $v$ consists of different letters.
\end{proof}

According to Lemma \ref{lemma_art_strong1}, the $k$-ary $\frac{k{-}2}{k{-}3}$-free words have two types of $(k{-}1)$-factors: \textit{quasipermutations}, consisting of different letters, and \textit{repeats}, in which the first and the last letter coincide. By \textit{permutation} we mean a $k$-factor consisting of different letters only.

\begin{rmrk} \label{kplus}
Abelian $\frac{k{+}1}{k{-}1}$-powers (respectively, $\frac{k{+}2}{k}$-powers) are forbidden for the $k$-ary $\frac{k{-}2}{k{-}3}$-free language whenever $k\ge 5$ (respectively, $k\ge 6$). 
\end{rmrk}

\begin{lmm} \label{lemma_art_strong2}
For $k\ge6$, any $k$-ary Abelian-$\frac{k{-}2}{k{-}3}$-free word beginning with a quasipermutation and containing no permutations as factors has length at most $4k{-}2$.
\end{lmm}

\begin{proof}
Let $w$ be a word satisfying the conditions of the lemma. Suppose that $j$th and $(j{+}1)$th $(k{-}1)$-factors of $w$ are quasipermutations. Then they consist of the same letters. Hence, the $(j{+}2)$th $(k{-}1)$-factor of $w$ is a repeat, otherwise $w$ contains an Abelian $\frac{k{+}1}{k{-}1}$-power, which is impossible by Remark~\ref{kplus}. 

Aimed at a contradiction, let $|w|\ge 4k{-}1$. Then the number of $(k{-}1)$-factors in $w$ is at least $3k{+}1$. Hence, $w$ contains at least $k$ repeats and also a quasipermutation to the right of the $k$th (counting from left to right) of these repeats. Since there are only $k$ possible sets of letters for quasipermutations, $w$ contains two quasipermutations, which consist of the same letters and are not successive. Let $i$th $(k{-}1)$-factor $z$ and $j$th $(k{-}1)$-factor $\bar{z}$ of $w$ be such quasipermutations such that the difference $j{-}i>1$ is minimal. If $z$ and $\bar{z}$ overlap in $w$, they form a factor $xy\bar{x}$ such that $xy=z$ and $y\bar{x}=\bar{z}$. Obviously, $|x|\ge2$ and $\bar{x}$ is an anagram of $x$. Thus, $xy\bar{x}$ is an Abelian $\beta$-power for some $\beta\ge\frac{k{+}1}{k{-}1}$, which is impossible by Remark~\ref{kplus}. 

Now suppose that $z$ and $\bar{z}$ do not overlap in $w$. Since two successive quasipermutations in $w$ consist of the same letters, by minimality of $j{-}i$ we get that the $(i{+}1)$th and the $(j{-}1)$th $(k{-}1)$-factors of $w$ are repeats. Consider the word $u=w_i\ldots w_{j{+}k{-}2}=zy\bar{z}$. By minimality of $j{-}i$, $u$ contains at most $k$ repeats, and thus, at most $3k$ $(k{-}1)$-factors. So we have $|u|\le 4k{-}2$. The word $u$ is an Abelian $\frac{|u|}{|u|{-}k{+}1}$-power. For $k\ge7$,
$$
\frac{|u|}{|u|-k+1}\ge\frac{4k-2}{3k-1}\ge\frac{k-2}{k-3},
$$
contradicting to the fact that $w$ is Abelian-$\frac{k{-}2}{k{-}3}$-free. A more detailed analysis is needed for $k=6$. We will prove that in this case the word $u$ contains less than $2k=12$ quasipermutations. If this number is achieved, $u$ contains five pairs of successive quasipermutations in addition to $z$ and $\bar{z}$. Then the beginning of $u$ looks as follows, up to the renaming of letters (recall that $u$ contains no permutations). Under each letter, the type of $(k{-}1)$-factor beginning with this letter is indicated (q = quasipermutation, r = repeat):
$$
\arraycolsep=1pt
\begin{array}{cccccccccccccc}
1&2&3&4&5&2&6&3&\pmb5&\pmb1&\pmb2&\pmb3&\pmb4&\ldots\\
\mathrm q&\mathrm r&\mathrm q&\mathrm q&\mathrm r&\mathrm q&\mathrm q&\mathrm r&\mathrm q&&&&&\ldots
\end{array}
$$
We see that $u$ contains another anagram of $z$ (written in boldface), a contradiction with the choice of $\bar{z}$. In fact, we proved that the sequence of $(k{-}1)$-factors of $u$ has no factor $\mathrm{qrqqrqqrq}$. Thus, the longest sequence of $(k{-}1)$-factors of $u$ is $\mathrm{qrqqrqrqqrqrqqrq}$. So we have $|u|\le 20$. Therefore, $u$ is an Abelian $(4/3)$-power, while $w$ is Abelian-$(4/3)$-free by conditions of the lemma. This contradiction concludes the proof.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{art_strong}]
Suppose that the exponent $\frac{k{-}2}{k{-}3}$ is Abelian-$k$-avoidable, and $W$ is a $k$-ary Abelian-$\frac{k{-}2}{k{-}3}$-free infinite word. First we consider the case $k\ge6$. By Lemmas \ref{lemma_art_strong1}, \ref{lemma_art_strong2}, infinitely many $k$-factors of $W$ are permutations. Note that at least one of any three successive $k$-factors of $W$ is not a permutation (otherwise, $W$ contains an Abelian $\frac{k{+}2}{k}$-power, which is impossible by Remark \ref{kplus}). So, we can pick a pair of indices $i,j$ such that $i{+}1<j$, $i$th and $j$th $k$-factors of $W$ are permutations, and $r$th $k$-factor of $W$ is not a permutation whenever $i<r<j$. 

If the two chosen permutations overlap in $W$, they form a factor $xy\bar{x}$ such that $|xy|=k$, $|x|\ge2$, and $\bar{x}$ is an anagram of $x$. This factor is an Abelian $\beta$-power for some $\beta\ge\frac{k{+}2}{k}$, which is impossible by Remark \ref{kplus}. On the other hand, if these permutations do not overlap in $W$, then $W$ has a factor $u=xy\bar{x}$ such that $x$ and $\bar{x}$ are permutations (and hence, anagrams of each other). If we delete the first and the last letters of $u$, we will get a $\frac{k{-}2}{k{-}3}$-free word which begins with a quasipermutation and contains no permutations as factors. By Lemma \ref{lemma_art_strong2}, $|u|{-}2\le 4k{-}2$, i.\,e. $|u|\le 4k$. Hence, $u$ contains an Abelian $\beta$-power for some $\beta\ge4/3$. This contradiction shows that $W$ cannot exist, so the exponent $\frac{k{-}2}{k{-}3}$ is Abelian-$k$-unavoidable for any $k\ge6$.

The case $k=5$ requires a separate analysis. This is a dull (although not very long) case examination. So, we omit it, giving only statistics confirmed by computer search: the antidictionary of the 5-ary $(3/2)$-free language contains only 49 lexmin words, and the maximum length of the root of such a word is 10.
\end{proof}

Now we move to weak Abelian powers. In what follows, we prove

\begin{thrm} \label{art_weak}
$ART_{w}(k) \ge \frac{k}{k{-}2}$ for all $k \ge 10$.
\end{thrm}

The proof of this theorem relies on two lemmas. We say that a letter $w_i$ of the word $w\in\Sigma^*$ is \textit{old} if $w_i = w_j$ for some $j < i$, and \textit{new} otherwise.

\begin{lmm} \label{lemma_art_weak1}
Suppose that $k \ge 8$, $w \in \Sigma^*$ is a $k$-ary weak Abelian-$\frac{k}{k{-}2}$-free word, $1\le l\le 4$, and $w$ ends with $l$ old letters. Then $2|w| > lk$.
\end{lmm}

\begin{proof}
All $l$ last letters of $w$ are different, otherwise they form a weak Abelian power of exponent at least $\frac{4}{3}$, which is greater than $\frac{k}{k{-}2}$ for $k \ge 8$. The last $l$ letters are old, so all of them occur somewhere in the word $w_{1} \ldots w_{|w|{-}l}$. Hence, $w$ is a weak Abelian power of exponent $\frac{|w|}{|w|{-}l} < \frac{k}{k{-}2}$, whence $2|w| > lk$.
\end{proof}

\begin{crllr} \label{coroll_art_weak}
Suppose that $k \ge 8$, $w = pqrs$ is a $k$-ary weak Abelian-$\frac{k}{k{-}2}$-free word, $|p| = |r| = \lfloor k/2 \rfloor$, $|q| = |s| = \lceil k/2 \rceil$. Then
\begin{itemize}
\item[(1)] $p$ contains no old letters;
\item[(2)] $pq$ contains no two successive old letters;
\item[(3)] $pqr$ contains no three successive old letters;
\item[(4)] $w = pqrs$ contains no four successive old letters.
\end{itemize}
\end{crllr}

\begin{proof}
If we consider a prefix of $pqrs$ ending with a group of successive old letters, we get the bound for the length of this group from Lemma~\ref{lemma_art_weak1}.
\end{proof}

\begin{rmrk} \label{remark_art_weak}
Suppose that $k \ge 8$, $w$ is a $k$-ary weak Abelian-$\frac{k}{k{-}2}$-free word, and $|w| = \lfloor\frac{k}{2}\rfloor$. Then $w$ consists of $\lfloor\frac{k}{2}\rfloor$ different letters.
\end{rmrk}

\begin{lmm} \label{lemma_art_weak2}
Suppose that $k \ge 10$, $w \in \Sigma^*$ is a $k$-ary weak Abelian-$\frac{k}{k{-}2}$-free word, and $|w| = 2k$. Then $w$ contains all $k$ letters from $\Sigma^*$.
\end{lmm}
\begin{proof}
Choose a word $w$ of length $2k$ in which any new letter appears as late as possible in view of Corollary~\ref{coroll_art_weak}. That is, if we write
$w=pqrs$, where $|p| = |r| = \lfloor\frac{k}{2}\rfloor$ and $|q| = |s| = \lceil\frac{k}{2}\rceil$, then each new letter in $q$ (in $r$, in $s$) follows one (respectively, two and three) old letters in $w$. We call such a word $w$ \textit{late}. Obviously, it is enough to prove that any late word contains $k$ new letters. We prove this by induction. For the inductive base $k=10$, the location of new letters in $w$ is given by the following on-\textit{encoding} (o\,=\,old, n\,=\,new):
\begin{equation}
\mathrm{nnnnn\,onono\,onoon\,ooono},
\end{equation}
so the required statement holds. We consider ``even'' ($k=2l{-}1$ to $2l$) and ``odd'' ($k=2l$ to $2l{+}1$) inductive steps separately. During even step, the length of $p$ and $r$ increases, while the length of $q$ and $s$ increases during odd step.

Even step is easy. Take the on-encoding of a late word $w=pqrs$ of length $2k$ and add $\mathrm n$ to its beginning and $\mathrm o$ to its end. If $r$ does not end by two old letters, then we get the on-encoding of a late word of length $2k{+}2$. Otherwise, to get such an on-encoding we should just move all the $\mathrm n$'s to the right of these two letters by one symbol to the left (because the first letter of $s$ has become the last letter of $r$). Anyway, a late word of length $2k{+}2=4l$ contains $k{+}1$ new letters. We also note that the last letter of the late word of length $4l$ is old (this assertion holds for the inductive base as well).

Now we prove the odd step. Let $v=p'q'r's'$ be a late word of length $2k{+}2$. We take the on-encoding of a late word $w=pqrs$ of length $2k=4l$, add $\mathrm o$ and $\mathrm n$ to its end, and compare the resulting word $z\in\{\mathrm{o,n}\}^*$ with the on-encoding of $v$. As was shown above, the last letter of $w$ is old:

\centerline{
\begin{picture}(90,22)(-5,-6)
\put(0,0){\line(1,0){85}}
\put(0,9){\line(1,0){85}}
\put(0,9){\line(0,-1){3}}
\put(20,9){\line(0,-1){3}}
\put(42.5,9){\line(0,-1){3}}
\put(62.5,9){\line(0,-1){3}}
\put(85,9){\line(0,-1){3}}
\put(0,0){\line(0,1){3}}
\put(20,0){\line(0,1){3}}
\put(40,0){\line(0,1){3}}
\put(60,0){\line(0,1){3}}
\put(80,0){\line(0,1){3}}
\put(1.4,4){\makebox(0,0)[cb]{\small n}}
\put(18.6,4){\makebox(0,0)[cb]{\small n}}
\put(21.4,4){\makebox(0,0)[cb]{\small o}}
\put(23.75,4){\makebox(0,0)[cb]{\small n}}
\put(41.4,4){\makebox(0,0)[cb]{\small o}}
\put(61.4,4){\makebox(0,0)[cb]{\small o}}
\put(78.6,4){\makebox(0,0)[cb]{\small o}}
\put(81.4,4){\makebox(0,0)[cb]{\small o}}
\put(83.75,4){\makebox(0,0)[cb]{\small n}}
\put(10,4.5){\makebox(0,0)[cb]{\small\ldots}}
\put(32,4.5){\makebox(0,0)[cb]{\small\ldots}}
\put(51,4.5){\makebox(0,0)[cb]{\small\ldots}}
\put(71,4.5){\makebox(0,0)[cb]{\small\ldots}}
\put(-2,-1.3){\makebox(0,0)[rt]{$w=$}}
\put(-2,11.8){\makebox(0,0)[rt]{$v=$}}
\put(-2,5.5){\makebox(0,0)[rt]{$z=$}}
\put(10,-1.5){\makebox(0,0)[ct]{\small $p$}}
\put(30,-1.5){\makebox(0,0)[ct]{\small $q$}}
\put(50,-1.5){\makebox(0,0)[ct]{\small $r$}}
\put(70,-1.5){\makebox(0,0)[ct]{\small $s$}}
\put(10,13){\makebox(0,0)[ct]{\small $p'$}}
\put(30,13){\makebox(0,0)[ct]{\small $q'$}}
\put(50,13){\makebox(0,0)[ct]{\small $r'$}}
\put(70,13){\makebox(0,0)[ct]{\small $s'$}}
\end{picture} }

The word $z$ contains $k{+}1$ $\mathrm n$'s. Each letter $\mathrm n$ in $z$, the position of which corresponds to the part $q'$ (part $r'$, part $s'$) of the word $v$, follows at least one (respectively, two and three) letters $\mathrm o$. The only possible exception is the last letter $\mathrm n$ in $z$. So, if $w$ ends with two old letters, then no exception occurs, and the position of $j$th new letter in $v$ is less than or equal to the position of $j$th letter $\mathrm n$ in $z$ for any $j=1,\ldots, k{+}1$. As a result, $v$ certainly contains $k{+}1$ new letters, and we are done. The case when the penultimate letter of $w$ is new implies the exception and is analyzed in the last part of the proof. 

\smallskip
Assuming that the on-encoding of $w$ ends with $\,\mathrm{no}$, we analyze three cases depending on the position $j$ of the first new letter in $s$. If $j$ is the second position of $s$, we shift all $\mathrm n$'s, corresponding to the part $s$ of $w$, by one symbol to the left in the word $z$. Since the position $j{-}1$ in this case corresponds to the part $r'$ of $v$, the obtained word $z'$ possesses the desired property: each letter $\mathrm n$, the position of which corresponds to the part $q'$ (part $r'$, part $s'$) of the word $v$, follows at least one (respectively, two and three) letters $\mathrm o$. As above, we conclude that $v$ contains $k{+}1$ new letters. If $j$ is the fourth position of $s$, then $l=|s|$ is odd, because the positions of new letters in $s$ are equal modulo 4. Then $q$ ends with an old letter, implying that the second letter of $r$ is new. We shift all $\mathrm n$'s, corresponding to the parts $r$ and $s$ of $w$, by one symbol to the left in the word $z$. Repeating the above argument, we get that $v$ contains $k{+}1$ new letters. 

It remains to consider the case when $j$ is the third position of $s$. Then $l=|s|$ is divisible by 4. Hence, the last letter of $q$ is new. Since the last letter of $q$ and the third letter of $s$ are new, the third and the penultimate letters of $r$ are also new. Therefore, $l=|r|=3l'{+}1$. Note that $q$ and $s$ contain $\frac{l}{2}$ and $\frac{l}{4}$ new letters, respectively, while $r$ contains $\frac{l{-}1}{3}$ new letters. Since $l=k/2\ge5$, we have $l\ge 16$. Then we have $\frac{l{-}1}{3} > \frac{l}{4}$, implying that $w$ contains more than $k$ new letters, a contradiction. The lemma is proved.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{art_weak}]
Let $w = uv$ is a $k$-ary word, $|u|=2k$, $v=\lfloor k/2 \rfloor$. Aimed at a contradiction, we assume that $w$ is a weak Abelian-$\frac{k}{k{-}2}$-free word. By Remark~\ref{remark_art_weak}, all letters in the word $v$ are different. By Lemma~\ref{lemma_art_weak2}, the word $u$ contains all $k$ letters. Hence, all letters of $v$ are contained in $u$, so $w$ is a weak Abelian power of exponent $\frac{2k + \lfloor k/2 \rfloor}{2k}$ which is not less than $\frac{k}{k{-}2}$ for $k \ge 10$. This is impossible as $w$ is weak Abelian-$\frac{k}{k{-}2}$-free.

So, any $k$-ary word of length at least $2k{+}\lfloor k/2 \rfloor$ has a forbidden factor. This means that the language of $k$-ary weak Abelian-$\frac{k}{k{-}2}$-free words is finite, implying $ART_{w}(k) \ge \frac{k}{k{-}2}$.
\end{proof}


\section{Antidictionaries of Abelian-power-free languages}

Now we prepare computer-assisted studies. Let $\beta >1$ be an extended rational number. In order to estimate the growth rate of the Abelian-$\beta$-free language by the method described in Sect.~1.3, we should construct the antidictionary of this language. If the language is infinite, the antidictionary is also infinite by Remark~\ref{infad}, so we actually construct its finite approximation. More precisely, we find all minimal forbidden words whose root is of length at most $R$ for some integer $R$. Next lemma easily follows from the definitions of Abelian fractional powers. 

\begin{lmm} \label{sym}
If a word $w \in \Sigma^{*}$ is a weak (semistrong, strong) Abelian $\beta$-power and $\sigma$ is a permutation of $\Sigma$, then
$\sigma(w)$ is also a weak (respectively, semistrong, strong) Abelian $\beta$-power.
\end{lmm}

Lemma~\ref{sym} tells us that Abelian-power-free languages are symmetric. Hence, it is not necessary to construct the whole antidictionary; we can construct just the trie of all lexmin words instead. We store all possible roots of lexmin words in an auxiliary queue $Q$, iterating over roots in the order of increasing length. Note that these roots should be lexicographically minimal words in their symmetry classes. For convenience, we store with each word in the queue the number of different letters in it. For each root $r$, we try to construct all minimal forbidden words from it and add them to a trie which stores the lexmin words found so far. After that, we try to extend the root by appending letters from $\Sigma$ to its end and push this longer root into the queue. Then we pop another root and continue the algorithm until all roots of length at most $R$ are handled, see procedure~\textsc{iterate} below. Recall that $\Sigma = \{1,\ldots,k\}$. \textsc{build} is a recursive procedure described below in p.\,\pageref{pr2}. Call of \textsc{build} at line~4 results in adding all lexmin forbidden words with the root $r$ to the trie.

\medskip
\noindent{\bf Procedure} \textsc{iterate} (outer cycle).
\texttt{\begin{tabbing}
01. push $('1';1)$ into $Q$\\
02. while \= $Q$ is not empty\\
03. \> pop $(r;t)$ from $Q$\\
04. \> \textsc{build}$(r,r,\vec{p}(r))$\\
05. \> if \= $|r| < R$\\
06. \>\> for \= each $c \le t$ such that $rc$ has no forbidden suffixes\\
07. \>\>\> push $(rc;t)$ into $Q$\\
08. \>\> if $t < k$\\
09. \>\>\> push $(r(t{+}1);t{+}1)$ into $Q$\\
10. end while
\end{tabbing}}
%\vspace*{-5mm}
The process of constructing all minimal forbidden words from a given root is quite time-consuming, as the number of these words can be very large. The dependence of their lengths on the length of the root is also not trivial, as the following lemma shows.

\begin{lmm} \label{lens}
If $w \in \Sigma^{*}$ is a minimal forbidden word for an Abelian-$\beta$-free language and the length of its root is equal to $R$, then
\begin{itemize}
\item[(1)] $|w| = \lceil R \cdot \beta \rceil$ for weak Abelian powers,
\item[(2)] $\lceil R \cdot \beta \rceil \le |w| \le R \cdot \lceil \beta \rceil$ for strong or semistrong Abelian powers, and this interval cannot be shortened in general.
\end{itemize}
\end{lmm} 

\begin{proof}
A minimal forbidden word for an Abelian-$\beta$-free language is at least an Abelian $\beta$-power, so the lower bound for $|w|$ follows from definitions. To prove (1), note that each prefix of a weak Abelian power is also a weak Abelian power with the same root. So, if the length of the word $w$ exceeds $\lceil R \cdot \beta \rceil$, $w$ will have a forbidden proper prefix. This note also proves the upper bound for (2) in view of Remark~\ref{abel1}\,(1). 
In the case of strong and semistrong Abelian powers the situation is more difficult, because not all their prefixes are Abelian powers. Thus, the Abelian square $abcde\,bdaec$ of length $10$ is also a minimal forbidden word for the strong (=\,semistrong) Abelian-$(7/5)$-free language, as one can check directly. This example proves that the upper bound in (2) is sharp.
\end{proof}

We construct lexmin forbidden words from a root recursively, appending letters to the end of a current word one by one until one of three exit conditions is fulfilled: current word is a lexmin forbidden word, current word is too long, or current word has a forbidden proper suffix. At each step we maintain the vector $\vec p$ of unused letters. When we append a letter $c$ to our word, we decrease the corresponding component $[\vec p]_c$ of $\vec p$. But if by appending a letter we finish appending an anagram of the root, the next letter can again be any letter in the root, so we make $\vec p$ equal to the Parikh vector of the root. The formal description of this construction is given by procedure~\textsc{build} whose arguments are the current word $w$, the root $r$, and the current vector of unused letters $\vec p$. \textsc{is\_abelian} is a subroutine which checks whether $w$ is a (weak, semistrong, strong) Abelian power with the root~$r$.

\smallskip
\noindent{\bf Procedure} \textsc{build}($w,r, \vec p$) (constructing forbidden words). \label{pr2}
\texttt{\begin{tabbing}
01. if \= \textsc{is\_abelian}($w,r$)\\
02. \> if \= $|w|$ satisfies Lemma \ref{lens}\\
03. \>\> add $w$ to the trie\\
04. \> exit procedure\\
05. if \= $|w|$ equals the upper bound from Lemma \ref{lens}\\
06. \> exit procedure\\
07. if \= $|w| \mod |r| = 0$\\
08. \> $\vec p = \vec p(r)$\\
09. for \= each letter $c$ such that $[\vec p]_c > 0$\\
10. \> $u = wc$\\
11. \> $\vec q = \vec p$\\
12. \> $[\vec q]_c = [\vec q]_c - 1$\\
13. \> if \= $u$ has no forbidden proper suffixes\\
14. \> \> \textsc{build}($u,r, \vec q$)\\
15. end for\\
\end{tabbing}}
\vspace*{-5mm}
If the conditions at lines 1 and 2 hold, then the word $w$ is an Abelian power with the root $r$ and its Abelian exponent is at least $\beta$. The word $w$ has no forbidden proper factors because (a) $r$ is Abelian-$\beta$-free by construction, see Procedure \textsc{iterate}, and (b) the condition at line 13 is checked on the previous steps of recursion for each prefix of $w$ which is longer than $r$. So, $w$ is indeed a minimal forbidden word and the operation at line 3 is justified.

We can easily maintain Parikh vectors of all prefixes of $w$. Therefore, we are able to calculate the Parikh vector of any factor of this word, subtracting the Parikh vectors of corresponding prefixes. This is enough to implement the subroutine \textsc{is\_abelian} in constant time for each of three definitions of Abelian fractional power, assuming that $\lfloor\beta\rfloor$ is a constant.

Finally, we have to check the condition at line 13 efficiently. The following lemmas are useful in special cases:

\begin{lmm} \label{integral}
If $\beta$ is an integer and $w \in \Sigma^{*}$ is an Abelian $\beta$-power, then the reversal of $w$ is also an Abelian $\beta$-power.
\end{lmm}

\begin{lmm} \label{weak1}
Suppose that $u, v, w \in \Sigma^{*}$, $u$ and $v$ are suffixes of $w$, and $\bar{u}$ ($\bar{v}$) is the shortest suffix of $w$, which is
a non-trivial weak Abelian power with the tail $u$ (respectively, $v$). If $|u| < |v|$, then $|\bar{u}| \le |\bar{v}|$.
\end{lmm}

\begin{proof}
Let $\bar{v} = \hat{v} v$. Then $\vec p(\hat{v}) \ge \vec p(v) \ge \vec p(u)$. It means that $\bar{v}$ is a weak Abelian
power with the tail $u$ by definition. But $\bar{u}$ is the shortest suffix of $w$ with such property, so $|\bar{u}| \le |\bar{v}|$.
\end{proof}

Now we can formulate the main lemma, which estimates the running time of the procedure that looks for the forbidden suffixes. We consider the size of the alphabet as a constant.%

\begin{lmm}
Let $w \in \Sigma^{*}$, $|w| = n$, $\beta > 1$. During our algorithm we can check whether $w$ has a suffix with Abelian exponent at least $\beta$:
\begin{itemize}
\item[(1)] in $O(n)$ time, if $\beta$ is an integer or if $\beta < 2$ and we consider weak Abelian powers;
\item[(2)] in $O(n^2)$ time in all other cases.
\end{itemize}
\end{lmm}

\begin{proof}
If $\beta$ is an integer, then at the moment we consider $w$ we can be sure that all shorter forbidden words are already stored in the trie.
According to \hbox{Lemma~\ref{integral}}, we can check prefixes of the reversal of the word $w$ instead of suffixes of $w$. So, we read the word $w$ backwards and replace the obtained word ``on the fly'' by the lexicographically minimal equivalent word. To do this replacement in $O(n)$ time, we store the images of replaced letters in an array of constant size. If the image of the current letter is undefined so far, it is set to the biggest existent image plus one. The obtained lexmin word is then considered as an input word for the current trie. If the trie reaches a terminal state, the forbidden prefix is detected. If the trie cannot reach such a state, then the input word has no forbidden prefixes. This check also takes linear time, so we are done with the integral powers.

Now suppose that $\beta$ is not an integer and $w$ has a forbidden suffix. Then its length is determined by the lengths of its tail and its root. We just try all possible values of these lengths (each of them does not exceed $n / \lfloor\beta\rfloor$) and check if the resulting suffix is actually a long enough Abelian power. This check is made in constant time by the subroutine \textsc{is\_abelian} we described earlier, thus giving us quadratic time overall. If $1 < \beta < 2$ and we consider weak Abelian powers, then, according to Lemma \ref{weak1}, the length of a suffix cannot decrease as we increase the length of its tail (note that Lemma~\ref{weak1} cares only about \textit{shortest} Abelian powers with the given tail). So, in this case the whole procedure takes linear time.
\end{proof}

\section{Numerical results}

We present some of the results on the growth rates of Abelian power-free languages. These results are related to integral Abelian powers and fractional Abelian powers that appear to be close to the Abelian repetition threshold. In most cases our algorithm allowed us to build any antidictionary $M_i$ such that the corresponding deterministic finite automaton (dfa) can be stored in the 2Gb memory of a PC. It means that our method in general proved efficient.

But we discovered that the sequences of upper bounds converge to the growth rate of the target languages extremely slow. For example, to get an upper bound for the growth rate of the binary ``usual'' cube-free language, one may take $R = 7$ and build a dfa with $246$ vertices; the bound given by this automaton deviates by less than 0,001 from the precise value of the growth rate. On the other hand, we have a numerical evidence that any of our non-zero upper bounds for Abelian-power-free languages is more than 0,01 away from the actual value. It appears that lots of words contain only long forbidden Abelian powers.

\begin{table}[!htb]
\caption {\small\sl Abelian-power-free languages for integral powers. The columns contain (from left to right):
size of the alphabet, avoidable exponent, maximum length of a root, number of lexmin words,
number of vertices in the dfa built from the trie of lexmin words, upper bound for the growth rate.
}
\label{table:integral_rates}
\tabcolsep=3pt
\centerline{\small
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\!|\Sigma|$ & Exponent & Root & Words & Vertices & Growth rate \\
\hline
2 & 4 & 12 & 8\,767\,762 & 41\,571\,476 & 1,374164 \\
\hline
3 & 3 & 8 & 6\,015\,458 & 15\,187\,934 & 2,371237 \\
\hline
4 & 2 & 20 & 4\,221\,881 & 23\,653\,900 & 1,444344 \\
\hline
5 & 2 & 10 & 6\,420\,827 & 16\,081\,994 & 3,227410 \\
\hline
\end{tabular}
}
\end{table}

Table~\ref{table:integral_rates} contains the calculated upper bounds for the growth rates of Abelian-$\beta$-free languages for integral numbers $\beta$. Using the described method, we were able to build antidictionaries containing millions of words. Although the obtained bounds are not very close to  exact values, they can be used to compare the relative ``sizes'' of Abelian-power-free languages, for example, the ternary cube-free language seems to be much larger than binary 4-free one.

\begin{table}[!htb]
\caption {\small\sl \textbf{Weak} Abelian-power-free languages. The explanations for the columns are the same as in Table~\ref{table:integral_rates}
}
\label{table:weak_rates}
\tabcolsep=3pt
\centerline{\small
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\!|\Sigma|$ & Exponent & Root & Words & Vertices & Growth rate \\
\hline
2 & 11/3 & --- & 13\,029 & --- & 0,000000 \\
\hline
2 & $(11/3)^{+}$ & 25 & 22\,440\,239 & 52\,403\,705 & 1,055275 \\
\hline
3 & 12/5 & --- & 556\,403 & --- & 0,000000 \\
\hline
3 & $17/7$ & 24 & 6\,128\,640 & 7\,500\,382 & 1,081150 \\
\hline
3 & $(17/7)^{+}$ & 25 & 26\,586\,251 & 32\,980\,908 & 1,108788 \\
\hline
4 & $(13/7)^{+}$ & --- & $>$2\,105\,968 & --- & 0,000000 \\
\hline
4 & $15/8$ & 31 & 1\,408\,013 & 7\,038\,325 & 1,101764 \\
\hline
4 & $(15/8)^{+}$ & 32 & 8\,069\,429 & 39\,242\,238 & 1,143995 \\
\hline
5 & 5/3 & --- & 18\,150 & --- & 0,000000 \\
\hline
5 & $(5/3)^{+}$ & 16 & 18\,285\,948 & 31\,618\,837 & 1,685733 \\
\hline
6 & 3/2 & --- & 434 & --- & 0,000000 \\
\hline
6 & $(3/2)^{+}$ & 16 & 7\,229\,321 & 9\,525\,614 & 1,493064 \\
\hline
7 & 3/2 & --- & $>$130\,486 & --- & 0,000000 \\
\hline
7 & $(3/2)^{+}$ & 11 & 7\,658\,103 & 4\,658\,332 & 3,580134 \\
\hline
8 & 7/5 & --- & 2\,710\,432 & --- & 0,000000 \\
\hline
8 & 10/7 & 16 & 28\,069\,579 & 23\,580\,728 & 1,506660 \\
\hline
8 & $(10/7)^{+}$ & 14 & 29\,486\,766 & 16\,420\,964 & 2,179884 \\
\hline
9 & 4/3 & --- & $>$343\,077 & --- & 0,000000 \\
\hline
9 & $(4/3)^{+}$ & 14 & 16\,240\,204 & 6\,943\,950 & 2,471691 \\
\hline
\end{tabular}
}
\end{table}
Table~\ref{table:weak_rates} is devoted to weak Abelian-power-free languages. The results listed in the table and some additional heuristics show that languages avoiding weak Abelian powers can have extremely large antidictionaries and still be finite. For example, we suppose that the languages of binary Abelian-$(11/3)^{+}$-free words and ternary Abelian-$(17/7)^{+}$-free words are finite, which makes finding the exact value of Abelian repetition threshold for small alphabets quite a challenging task.

\begin{table}[!htb]
\caption {\small\sl \textbf{Semistrong} Abelian-power-free languages.
The explanations for the columns are the same as in Table~\ref{table:integral_rates}.
}
\label{table:semi_rates}
\tabcolsep=3pt
\centerline{\small
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\!|\Sigma|$ & Exponent & Root & Words & Vertices & Growth rate \\
\hline
2 & 11/3 & --- & 14\,120 & --- & 0,000000 \\
\hline
2 & $(11/3)^{+}$ & 21 & 12\,706\,824 & 42\,549\,418 & 1,137926 \\
\hline
3 & $2^{+}$ & 20 & 5\,923\,132 & 19\,078\,136 & 1,266646 \\
\hline
\end{tabular}
}
\end{table}

Table~\ref{table:semi_rates} describes the Abelian-power-free languages for semistrong Abelian powers. The antidictionary of Abelian-square-free language over ternary alphabet contains only 7 lexmin words, but the ternary Abelian-$2^{+}$-free language seems to be exponential in case of semistrong Abelian powers. To justify Remark~\ref{abel2}, it is enough to compare this table with Table~\ref{table:strong_rates}.

\begin{table}[!htb]
\caption {\small\sl \textbf{Strong} Abelian-power-free languages.
The explanations for the columns are the same as in Table~\ref{table:integral_rates}.
}
\label{table:strong_rates}
\tabcolsep=3pt
\centerline{\small
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\!|\Sigma|$ & Exponent & Root & Words & Vertices & Growth rate \\
\hline
2 & 18/5 & --- & $>$1\,378\,225 & --- & 0,000000 \\
\hline
2 & 11/3 & 34 & 10\,199\,584 & 57\,443\,698 & 1,020862 \\
\hline
2 & $(11/3)^{+}$ & 16 & 16\,393\,356 & 67\,193\,118 & 1,232531 \\
\hline
3 &  $2^{+}$ & 13 & 12\,113\,648 & 37\,673\,788 & 1,645532 \\
\hline
4 & 9/5 & --- & 25\,684 & --- & 0,000000 \\
\hline
4 & $(9/5)^{+}$ & 30 & 3\,116\,205 & 17\,942\,923 & 1,175199 \\
\hline
5 & 3/2 & --- & 49 & --- & 0,000000 \\
\hline
5 & $(3/2)^{+}$ & 13 & 6\,999\,188 & 21\,445\,164 & 2,334839 \\
\hline
6 & $(4/3)^{+}$ & 21 & 9\,153\,227 & 36\,992\,553 & 1,482134 \\
\hline
7 & $(5/4)^{+}$ & 22 & 2\,957\,234 & 12\,260\,556 & 1,472652 \\
\hline
8 & $(6/5)^{+}$ & 22 & 3\,165\,822 & 10\,035\,601 & 1,551357 \\
\hline
\end{tabular}
}
\end{table}

Our last Table~\ref{table:strong_rates} describes strong Abelian-power-free languages. Here we can notice substantial gaps between the growth rates (and between the sizes of recognizing automata) that are due to the ``allowance'' of short factors with Abelian exponent $\beta$. For example, the allowance of a word $aba$ results in a huge gap of more than 2 in the growth rate for the Abelian-$(3/2)^{+}$-free language over the 5-letter alphabet. Unlike results for the weak Abelian powers, the data in Table~\ref{table:strong_rates} provides a strong evidence that the corresponding exponents coincide with the actual values of Abelian repetition threshold for strong Abelian powers, so we are able to formulate the following

\begin{cnjctr} \label{conj_strong}
The Abelian repetition threshold for strong and semistrong Abelian powers is given by
\begin{equation*}
ART_{s}(k) = 
\begin{cases}
  11/3, & k = 2, \\
  2, & k = 3,\\
  9/5, & k = 4,\\
  (k{-}2)/(k{-}3), & k \ge 5.
\end{cases}
\end{equation*}
\end{cnjctr}

\begin{thebibliography}{99}

\bibitem{ACR}
A. Aberkane, J. D. Currie, N. Rampersad, {\it The number of ternary words avoiding Abelian cubes grows exponentially}, 
J. Int. Seq., {\bf7} (2004), \#04.2.7, 13 pp. (electronic).

\bibitem {Bra}
F.-J. Brandenburg, {\it Uniformly growing $k$-th power free homomorphisms},
Theor. Comput. Sci., {\bf 23} (1983), 69-82.

\bibitem{Car}
A. Carpi, {\it On Dejean's conjecture over large alphabets}, Theor. Comput. Sci., {\bf 385} (2007), 137--151.

\bibitem{Car1}
A. Carpi, {\it On the number of Abelian square-free words on four letters}, Discr. Appl. Math., {\bf 81} (1998), 155--167.

\bibitem {CMR}
M. Crochemore, F. Mignosi, A. Restivo, {\it Automata and forbidden words}, Inform. Processing Letters, {\bf 67}(3) (1998), 111-117.

\bibitem{Cur}
J.\,D. Currie, {\it The number of binary words avoiding Abelian fourth powers grows exponentially}, Theor. Comput. Sci., {\bf319}(1--3) (2004), 441--446.

\bibitem {CR}
J.\,D. Currie, N. Rampersad, {\it A proof of Dejean's conjecture}, Mathematics of Computation (2010). DOI: 10.1090/S0025-5718-2010-02407-X 

\bibitem {Dej}
F. Dejean, {\it Sur un Th\'eor\`eme de Thue}, J. Comb. Theory A {\bf13}(1) (1972), 90-99.

\bibitem {Dek}
F.\,M. Dekking, {\it Strongly non-repetitive sequences and progression-free sets}, J. Combin. Theory A {\bf27} (1979), 181-185.

\bibitem {Erd}
P. Erd\"os, {\it Some unsolved problems}, Magyar Tud. Akad. Mat. Kutat\'o Int. K\"ozl. {\bf6} (1961), 221--264.

\bibitem {Ker}
V. Ker\"anen, {\it Abelian squares are avoidable on 4 letters}, Proc. ICALP'92, 41--52. Springer, Berlin, 1992. (LNCS {\bf 623}).

\bibitem{Ker2}
V. Ker\"anen, {\it A powerful abelian square-free substitution over 4 letters}, Theor. Comput. Sci. {\bf 410} (2009), 3893--3900.

\bibitem {Rao}
M. Rao, {\it Last Cases of Dejean's Conjecture}, Proceedings of the 7th International Conference on Words, Salerno, Italy. -- 2009. \#115.

\bibitem {Sh08ita}
A.M. Shur, {\it Comparing complexity functions of a language and its extendable part}, RAIRO Theor. Inf. Appl. {\bf42} (2008), 647--655.

\bibitem {Sh10tcs}
A.\,M. Shur, {\it Growth rates of complexity of power-free languages}, Theor. Comput. Sci. {\bf 411} (2010), 3209--3223.

\bibitem {Th}
A. Thue, {\it \"Uber unendliche Zeichenreihen}, Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl., Christiana {\bf 7} (1906), 1-22.

\end{thebibliography}

\end{document}